package com.gitee.feizns.explore.data_structure.linked_list.singly.isSubPath;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;
import com.gitee.feizns.explore.data_structure.tree.bs.easy.TreeNode;

/**
 * @author feizns
 * @since 2020/3/6
 */
public class IsSubPath {

    public static void main(String[] args) {

    }

    public static boolean isSubPath(ListNode head, TreeNode root) {
        if ( head != null && root != null ) {
            return isPath(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
        }
        return false;
    }

    private static boolean isPath(ListNode head, TreeNode root) {
        if ( head != null && root != null ) {
            if ( head.val != root.val )
                return false;
            if ( head.next == null )
                return true;
            return isPath(head.next, root.left) || isPath(head.next, root.right);
        }
        return false;
    }

}
